# -*- coding: utf-8 -*-

"""剑指 Offer II 104. 排列的数目
给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。
题目数据保证答案符合 32 位整数范围。

示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：
输入：nums = [9], target = 3
输出：0

提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000"""


class Solution:
    """这道题用回溯好解决，用动态规划也联想到 f(target) = f(target-nums[0]), f(target-nums[1]),...
    但是就是摸不准等号左右的关系，看例子上 f(4) = f(4-1) + f(4-2) + f(4-3)，但是理解不了这种关系的逻辑。
    后面看题解，应该重新捋下这个逻辑观念，题解上说，和为 4 的组合应该分成三类，以 1 结尾的组合数，以 2 结尾的组合数，以 3 为结尾的组合数，
    观念转变后，f(target) = f(target-nums[0])+f(target-nums[1])+f(target-nums[2])+...
               f(0) = 1，哪个元素都不用的空组合"""
    def combinationSum4(self, nums, target: int) -> int:
        memory = {0:1}
        def optimal(target):
            if target < 0:
                return 0

            if target == 0:
                return 1
            
            total_combs = 0
            for n in nums:
                if (subtarget := target-n) in memory:
                    combs = memory[subtarget]
                else:
                    combs = optimal(subtarget)
                    memory[subtarget] = combs
                total_combs += combs
            return total_combs
        return optimal(target)


if __name__ == '__main__':
    so = Solution()
    print(so.combinationSum4(nums = [1,2,3], target = 4))
    print(so.combinationSum4(nums = [9], target = 3))
    print(so.combinationSum4(nums = [9,10], target = 19))
